package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/20 14:44
 */
public class C877 {

    public static boolean stoneGame(int[] piles) {
        int before = before(piles, 0, piles.length - 1);
        int after = after(piles, 0, piles.length - 1);
        return before > after;
    }

    // 先手
    public static int before(int[] plies, int l, int r) {
        if (l == r) return plies[l];
        return Math.max(plies[l] + after(plies, l + 1, r), plies[r] + after(plies, l, r - 1));
    }

    // 后手
    public static int after(int[] plies, int l, int r) {
        if (l == r) return 0;
        return Math.min(before(plies, l + 1, r), before(plies, l, r - 1));
    }

    public static boolean dp(int[] piles) {
        int n = piles.length;
        int[][] before = new int[n][n];
        int[][] after = new int[n][n];
        // 对角线, l==r先手会选掉, 后手没机会
        for (int i = 0; i < n; i++) {
            before[i][i] = piles[i];
        }

        // 斜着填, 从右下,到左上, 先手后手一起填
        // [2, 3] [1, 2] [0, 1]
        // [1, 3] [0, 2]
        // [0, 3]

        // 对角线填过还需要填 n-1次
        for (int i = 1; i <= n - 1; i++) {
            int r = n - i - 1;
            int c = n - 1;
            while (r >= 0) {
                before[r][c] = Math.max(piles[r] + after[r + 1][c], piles[c] + after[r][c - 1]);
                after[r][c] = Math.min(before[r + 1][c], before[r][c - 1]);
                r--;
                c--;
            }
        }
        return before[0][n-1] > after[0][n-1];
    }


    // for test
    public static void main(String[] args) {
        int[] piles = {5, 3, 4, 5};
        System.out.println(stoneGame(piles));
        System.out.println(dp(piles));
    }

}
